package solver;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Random;

import model.IncrementalCostCalculator;
import model.SolverEnvironment;
import model.Process;
import model.Problem;
import model.Solution;

import org.jgrapht.graph.DefaultWeightedEdge;


import etm.core.monitor.EtmPoint;

public class SolutionConstructor extends BaseSolver{

//	public SolutionConstructor(Problem problem, Solution initialSolution) {
//		super(problem, initialSolution);
//		// TODO Auto-generated constructor stub
//	}
//
//	private SolverEnvironment env;
//	private Deque<Integer> taboo_exams;
//	private final int TABOO_LIMIT = 10;
//	private final int CANDIDATE_LIST_SIZE = 10;
//	private List<Integer> removedExams;
//	private String orderingType;
//
	public SolutionConstructor(SolverEnvironment env){
		super(env);
//		taboo_exams = new ArrayDeque<Integer>();
//		removedExams = new ArrayList<Integer>();
//		orderingType = "LWD";
	}
//
//	public void setOrderingType(String ot) {
//		orderingType = ot;
//	}
//
//	public void constructSolution() {
//		int attempt = 0;
//		double max_completion = 0.0;
//		while (!env.areAllProcessesAssigned()) {
//			attempt++;
//			if (attempt > 10000) {
////				logger.debug("LIMIT OF 10000 iterations reached");
//				break;
//			}
////			logger.debug("");
////			logger.debug(String.format("Start of attempt %d", attempt));
//			int sel_proc_id, sel_mach_id;
//			sel_proc_id = selectExam();
////			logger.debug("Selected exam " + sel_exam_id);
//			sel_mach_id = selectPeriod(sel_proc_id);
//			if (sel_mach_id == -1) {
//				sel_mach_id = rollback(sel_proc_id);
//			}
//			// System.out.printf("Selected exam=%d period=%d\n", sel_exam_id,
//			// sel_period_id);
//			getCurrentSolution().assignProcessToMachine(sel_proc_id, sel_mach_id);
////			logger.debug(String.format("ADD    %s period %d cost=%.4f [%s]",
////					problem.getExam(sel_exam_id), sel_period_id,
////					bb.getAverageCachedCostPerStudent(), bb.completionInfo()));
////			// logger.info(bb.completionInfo());
//		}
//		for (int i = 0; i < env.getProblem().P; i++) {
//			boolean success= attempt_greedy_reposition_exam(i);
////			if (success) {
////				System.out.printf("Exam %d repositioned succesfully\n", i);
////			} else {
////				System.out.printf("Exam %d could not be repositioned\n", i);
////			}
//		}
//		if (getCurrentSolution().percentageCompleted() > max_completion)
//			max_completion = getCurrentSolution().percentageCompleted();
////		logger.debug(String.format("Max percentage completed %.2f",
////				max_completion));
//	}
//
	@Override
	public int solveWithTimeLimit(int seconds) throws Exception {
		// TODO Auto-generated method stub
		return 0;
	}
//
//	public void reconstructSolution() {
//		Problem problem = env.getProblem();
//		IncrementalCostCalculator icc = env.getCostCalculator();
//		Solution pot_sol = env.getPotentialSolution();
//		long cost = icc.getNewSolutionCost();
//		double averageCost = cost / problem.P;
//		ArrayList<Integer> removeList = new ArrayList<Integer>();
//		for (int i = 0; i < problem.P; i++) {
//			if (-icc.getProcessRemoveProfit(pot_sol, i) > ((averageCost) / 2))
//				removeList.add(i);
//		}
//		for (Integer r : removeList) {
//			pot_sol.removeProcess(r.intValue());
//		}
//		constructSolution();
//
//	}
//
//	private int selectExam() {
//		if (!removedExams.isEmpty()) {
//			int sel_ex_id = removedExams.get(0);
////			logger.debug(String.format(
////					"Exam selected from recently removed exams %s",
////					removedExams));
//			removedExams.remove(new Integer(sel_ex_id));
//			return sel_ex_id;
//		}
//		Problem problem = env.getProblem();
//		if (orderingType.equalsIgnoreCase("LD")) {
//			Map<Integer, Integer> examids_values_dict = problem.getDegrees(bb);
//			return selectIdPriorityMaxValue(examids_values_dict);
//		} else if (orderingType.equalsIgnoreCase("SD")) {
//			Map<Integer, Integer> examids_values_dict = problem
//					.getSaturationDegrees(bb);
//			return selectIdPriorityMinValue(examids_values_dict);
//		} else if (orderingType.equalsIgnoreCase("RE")) {
//			Map<Integer, Integer> examids_values_dict = problem.getRemovals(bb);
//			return selectIdPriorityMaxValue(examids_values_dict);
//		} else if (orderingType.equalsIgnoreCase("EN")) {
//			Map<Integer, Integer> examids_values_dict = problem
//					.getEnrolments(bb);
//			return selectIdPriorityMaxValue(examids_values_dict);
//		} else if (orderingType.equalsIgnoreCase("LWD")) {
//			Map<Integer, Integer> examids_values_dict = problem
//					.getWeightedDegrees(bb);
//			return selectIdPriorityMaxValue(examids_values_dict);
//		}
//		throw new IllegalStateException("No such ordering " + orderingType);
//	}
//
//	private int selectIdPriorityMaxValue(Map<Integer, Integer> id_value_dict) {
//		int[] values = new int[id_value_dict.size()];
//		int[] ids = new int[id_value_dict.size()];
//		int i = 0;
//		for (Integer id : id_value_dict.keySet()) {
//			ids[i] = id;
//			values[i] = id_value_dict.get(id);
//			i++;
//		}
//		int n = CANDIDATE_LIST_SIZE;
//		if (n > values.length)
//			n = values.length;
//		partialSort(ids, values, n);
////		logger.debug("Ids " + Arrays.toString(ids));
//		return ids[roulette(values, n)];
//	}
//
//	private int selectIdPriorityMinValue(Map<Integer, Integer> id_value_dict) {
//		int[] values = new int[id_value_dict.size()];
//		int[] ids = new int[id_value_dict.size()];
//		int i = 0;
//		int max = 0;
//		for (Integer id : id_value_dict.keySet()) {
//			int v = id_value_dict.get(id);
//			if (v > max)
//				max = v;
//		}
//		for (Integer id : id_value_dict.keySet()) {
//			ids[i] = id;
//			values[i] = max - id_value_dict.get(id);
//			i++;
//		}
//		int n = CANDIDATE_LIST_SIZE;
//		if (n > values.length)
//			n = values.length;
//		partialSort(ids, values, n);
////		logger.debug("Ids " + Arrays.toString(ids));
//		return ids[roulette(values, n)];
//	}
//
//	// sorts the first topX greater values
//	private void partialSort(int[] ids, int[] values, int topX) {
//		int N = ids.length;
//		if (topX > N)
//			throw new IllegalArgumentException(
//					"topX should be no larger than the size of the array");
//		else if (topX == N)
//			topX--;
//		for (int i = 1; i < topX + 1; i++)
//			for (int j = N - 1; j >= i; j--) {
//				if (values[j - 1] < values[j]) {
//					int temp = values[j - 1];
//					values[j - 1] = values[j];
//					values[j] = temp;
//
//					int temp2 = ids[j - 1];
//					ids[j - 1] = ids[j];
//					ids[j] = temp2;
//				}
//			}
//	}
//
//	private int rollback(int sel_proc_id) {
////		EtmPoint point = etmMonitor.createPoint("SolutionConstructor:rollback");
//		Problem problem = env.getProblem();
//		Solution pot_sol = env.getPotentialSolution();
//		Map<Integer, Integer> machine_ids_values_dict = new HashMap<Integer, Integer>();
//		outer_loop: for (int i = 0; i < problem.P; i++) {
//			List<Integer> offended_processes = pot_sol.getAssignedProcessesInConflictWith(
//					sel_proc_id, i);
//			int sum = 0;
//			for (Integer ex_id : offended_exams) {
//				if (taboo_exams.contains(ex_id))
//					continue outer_loop;
//				Process exam = problem.getProcesses().get(ex_id);
//				sum = sum + exam.getRemovals();
//			}
//			machine_ids_values_dict.put(i, sum);
//		}
//		int vic_per_id;
//		if (machine_ids_values_dict.isEmpty()) {
//			vic_per_id = random.nextInt(problem.P);
////			logger.debug("Random selection among all periods");
//		} else {
//			vic_per_id = selectIdPriorityMinValue(machine_ids_values_dict);
////			logger.debug("***" + periodids_values_dict);
////			logger.debug(String.format("Period %d selected among %d periods",
////					vic_per_id, periodids_values_dict.size()));
//		}
//		List<Integer> offended_exams = bb.getScheduledExamsInConflictWith(
//				sel_proc_id, vic_per_id);
//		Process exam1 = problem.getProcesses().get(sel_proc_id);
//		for (Integer ex_id : offended_exams) {
//			boolean success = attempt_reposition_exam(ex_id);
//			if (!success) {
//				Process exam2 = problem.getProcesses().get(ex_id);
//				getCurrentSolution().removeProcess(ex_id);
//				removedExams.add(ex_id);
//				exam1.addRemovals(exam2.getEnrolments());
////				logger.debug(String.format(
////						"REMOVE %s from period %d cost=%.4f [%s]", exam2,
////						vic_per_id, bb.getAverageCachedCostPerStudent(),
////						bb.completionInfo()));
//			}
//		}
//		addTaboo(sel_proc_id);
//		return vic_per_id;
//	}
//
//	public boolean attempt_reposition_exam(int exam_id) {
//		int first_non_improving_reposition = -1;
//		int current_period = getCurrentSolution().getMachineIdForProcessId(exam_id);
//		long current_cost = cc.getNewSolutionCost();
//		int start = random.nextInt(problem.P);
//		for (int _i = start; _i < problem.P + start; _i++) {
//			int i = _i % problem.P;
//			if (i == current_period)
//				continue;
//			if (!iv.isFeasible(exam_id,current_period,i)) {
//				if(current_period!=-1)
//					getCurrentSolution().removeProcess(exam_id);
//				getCurrentSolution().assignProcessToMachine(exam_id, i);
//				long new_cost = cc.getPotentialSolutionCost();
////				logger.debug(String
////						.format("MOVED Exam=%d from period %d to period %d cost=%.4f [%s]",
////								exam_id, current_period, i,
////								bb.getAverageCachedCostPerStudent(),
////								bb.completionInfo()));
//				if (new_cost < current_cost) {
////					logger.debug("diff cost = " + (new_cost - current_cost));
//					return true;
//				} else if (first_non_improving_reposition == -1) {
//					first_non_improving_reposition = i;
//				}
//				if(current_period!=-1){
//					bb.unschedule(exam_id);
//					bb.schedule(exam_id, current_period);
//				}
//				
//			}
//		}
//		if (first_non_improving_reposition == -1) {
//			bb.unschedule(exam_id);
//			bb.schedule(exam_id, current_period);
//			return false;
//		} else {
//			bb.unschedule(exam_id);
//			bb.schedule(exam_id, first_non_improving_reposition);
//			return true;
//		}
//	}
//
//	public boolean attempt_greedy_reposition_exam(int exam_id) {
//		int current_period = bb.getScheduledPeriodFor(exam_id);
//		int current_cost = bb.getCachedCost();
//		int start = random.nextInt(problem.P);
//		for (int _i = start; _i < problem.P + start; _i++) {
//			int i = _i % problem.P;
//			if (i == current_period)
//				continue;
//			if (!bb.hasConflict(exam_id, i)) {
//				if(current_period!=-1)
//					bb.unschedule(exam_id);
//				bb.schedule(exam_id, i);
//				int new_cost = bb.getCachedCost();
//				logger.debug(String
//						.format("MOVED Exam=%d from period %d to period %d cost=%.4f [%s]",
//								exam_id, current_period, i,
//								bb.getAverageCachedCostPerStudent(),
//								bb.completionInfo()));
//				if (new_cost < current_cost) {
//					logger.debug("diff cost = " + (new_cost - current_cost));
//					return true;
//				}
//				if(current_period!=-1){
//					bb.unschedule(exam_id);
//					bb.schedule(exam_id, current_period);
//				}
//				else
//					current_period=i;
//			}
//		}
//		return false;
//	}
//
//	private void addTaboo(int selExamId) {
//		if (taboo_exams.size() == TABOO_LIMIT)
//			taboo_exams.removeFirst();
//		taboo_exams.addLast(selExamId);
//		logger.debug(String.format("Exam %d added to the taboo list %s",
//				selExamId, taboo_exams));
//	}
//
//	private int selectPeriod(int sel_ex_id) {
//		List<Integer> aList = new ArrayList<Integer>();
//		for (int p_id = 0; p_id < problem.P; p_id++) {
//			if (!bb.hasConflict(sel_ex_id, p_id))
//				aList.add(p_id);
//		}
//		if (aList.isEmpty())
//			return -1;
//		else {
//			int[] tmp = new int[aList.size()];
//			int i = 0;
//			int min = Integer.MAX_VALUE;
//			Map<Integer, Integer> periodids_values_dict = new HashMap<Integer, Integer>();
//			for (Integer period_id : aList) {
//				bb.schedule(sel_ex_id, period_id);
//				tmp[i] = bb.getCachedCost();
//				if (tmp[i] < min)
//					min = tmp[i];
//				i++;
//				bb.unschedule(sel_ex_id);
//			}
//			for (i = 0; i < tmp.length; i++) {
//				periodids_values_dict.put(aList.get(i), tmp[i] - min);
//			}
//			return selectIdPriorityMinValue(periodids_values_dict);
//		}
//	}
//
//	private int roulette_OLD(int[] array, int n) {
//		Random random = env.getRandom();
//		int sum = 0;
//		for (int i = 0; i < n; i++) {
//			sum += array[i];
//		}
//		if (sum == 0) {
////			logger.debug("The sum of all elements in array is zero "
////					+ Arrays.toString(array));
//			return random.nextInt(n);
//		}
//		double sphere = random.nextDouble();
//		int sum2 = 0;
//		int result = -1;
//		int i = 0;
//		do {
//			sum2 += array[i];
//			if ((double) sum2 / (double) sum > sphere)
//				result = i;
//			i++;
//		} while (result == -1);
//		// logger.debug(String.format("Winner:%d %s", result, Arrays
//		// .toString(array)));
//		return result;
//	}
//
//	private int roulette(int[] array, int n) {
//		int[] n_array = new int[n];
//		int v = n;
//		for (int i = 0; i < n; i++) {
//			n_array[i] = v;
//			v--;
//		}
//		return roulette_OLD(n_array, n);
//	}
//	
//	public void createInitColor(){
//		org.jgrapht.experimental.alg.color.BrownBacktrackColoring<Integer, DefaultWeightedEdge> colBrGen = 
//			new org.jgrapht.experimental.alg.color.BrownBacktrackColoring<Integer, DefaultWeightedEdge>(problem.getGraph());
//		
//		util.ConfictMatrixColoring<Integer, DefaultWeightedEdge> colGen = new 
//			util.ConfictMatrixColoring<Integer, DefaultWeightedEdge>(problem.getGraph());
////		System.out.println("Coloring UB "+colGen.getUpperBound(null));
//		int[] colors = colGen.largestSaturationFirstOrder();
////		System.out.println(Arrays.toString(colors));
//		int k=0;
//		for(int i=0; i<problem.P;i++){
//			while(!bb.hasConflict(colors[k], i)){
//				bb.schedule(colors[k], i);
//				k++;
//			}
//		}		
//	}
	
//	@Override
//	public int solveWithTimeLimit(int seconds) throws Exception {
//		
//		return 0;
//	}

}
